const arr = [10, 8, 9, 6, 5, 1, 4, 5, 3];
//冒泡排序：相邻比较
const maopaoSort = function (arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j < len; j++) {
            if (arr[i] > arr[j]) {
                // var temp = arr[j];
                // arr[j] = arr[i];
                // arr[i] = temp;
                [arr[j], arr[i]] = [arr[i], arr[j]];
            }
        }
    }
    return arr;
};

//选择排序：第1轮依次找出最小的，和第1个进行交换。第2轮，从第2个开始，再找出最小的，和第2个交换
const selectSort = function (arr) {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    }
    return arr;
};

// maopaoSort(arr);

// selectSort(arr);

/**
 * 插入排序
 * 整体思想是先从前往后排序，先前2个，再前3个，这样依次排下来，顺序是已经固定的
 * 所以，如果运气好，当前元素与相邻的元素一比较，刚好比它大，就不需要换位；而如果比相邻元素小，这俩换位，换完后，它再跟之前的元素比较，判断是否要换位
 */
const insertSort = function (arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        let preIndex = i - 1; //相邻元素索引
        let current = arr[i]; //当前元素
        while (preIndex >= 0 && current < arr[preIndex]) { //第2个小于第1个时，把第2个交换给第1个
            [arr[preIndex], arr[preIndex + 1]] = [arr[preIndex + 1], arr[preIndex]]; // [3, 2] = [2, 3], [2, 1] = [1, 2]
            preIndex--;
        }
    }
    return arr;
};

// insertSort(arr);

/**
 * 快速排序
 * 思想是先切割成2部分，分别比较，小的放左，大的放右，再递归处理
 */
const quickSort = function (arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const currentIndex = Math.floor(arr.length / 2);
    const current = arr[currentIndex];
    const left = [];
    const right = [];
    arr.forEach(function (item, index) {
        if (currentIndex != index) {
            if (item < current) {
                left.push(item);
            } else {
                right.push(item);
            }
        }
    });
    return quickSort(left).concat(current, quickSort(right))
};
// const quickSort = function (arr) {
//     const func = function (arr, start = 0, end = arr.length -1) {
//         // if (arr.length <= 1) {
//         //     return arr;
//         // }
//         const currentIndex = Math.floor(arr.length / 2);
//         var current = arr[currentIndex];
//         // var left = [];
//         // var right = [];
//         arr.forEach(function (item, index) {
//             if (currentIndex != index) {
//                 if (item < current) {
//                     // left.push(item);

//                 } else {
//                     // right.push(item);
//                    [arr[index], arr[currentIndex]] 
//                 }
//             }
//         });
//         left = func(left);
//         right = func(right);
//         return [left, current, right];
//     };
//     var res = func(arr);
//     return res.flat(Infinity);
// };

var arr2 = quickSort(arr);
console.log(arr2);